#pragma once
#include <iostream>
#include <vector>

using namespace std;

namespace close_hash
{
enum Status
{
    EMPTY,
    EXITS,
    DELETE
};

template <class K, class V>
struct HashData
{
    pair<K, V> _kv;
    Status _status = EMPTY;
};

template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return key;
    }
};

//特化——对string类型进行单独处理
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for(size_t i = 0; i < key.size(); i++)
        {
            hash *= 131;        //BKDR Hash思想
            hash += key[i];
        }
        return hash;
    }
};

struct HashFuncString
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for(size_t i = 0; i < key.size(); i++)
        {
            hash *= 131;        //BKDR Hash思想
            hash += key[i];
        }
        return hash;
    }
};

template <class K, class V, class Hash = HashFunc<K>>
class HashTable
{
private:
    vector<HashData<K, V>> _tables;
    size_t _n = 0;   //存储有效数据的个数
public:
    HashData<K, V>* Find(const K& key)
    {
        if(_tables.size() == 0)
        {
            return nullptr;
        }
        Hash hf;
        size_t start = hf(key) % _tables.size();
        size_t i = 0;
        size_t index = start + i;
        while(_tables[index]._status != EMPTY)
        {
            if(_tables[index]._kv.first == key
               && _tables[index]._status == EXITS)
            {
                return &_tables[index];
            }
            else
            {
                i++;
//                index = start + i;    //线性探测
                index = start + i * i;  //二次探测
                index %= _tables.size();
            }
        }
        
        return nullptr;
    }
    
    bool insert(const pair<K, V>& kv)
    {
        if(Find(kv.first))
        {
            return false;
        }
        
        if(_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
        {
            size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
            HashTable<K, V, Hash> newHT;
            newHT._tables.resize(newSize);
            for(auto &e: _tables)
            {
                if(e._status == EXITS)
                {
                    newHT.insert(e._kv);
                }
            }
            _tables.swap(newHT._tables);
  /*这里不用手动释放newHT的内存吗？
   newHT作为临时变量，出了作用域自动调用其成员的析构函数，vector的析构函数会清空内存的*/
        }
        Hash hf;
        size_t start = hf(kv.first) % _tables.size();
        size_t i = 0;
//        size_t index = start + i;     //线性探测
        size_t index = start + i * i;   //二次探测
        while(_tables[index]._status == EXITS)
        {
            index++;
            if(index == _tables.size())
            {
                index = 0;
            }
        }
        
        _tables[index]._kv = kv;
        _tables[index]._status = EXITS;
        _n++;
        
        return true;
    }
    
    bool erase(const K& key)
    {
        HashData<K, V>* ret = Find(key);
        if(ret == nullptr)
        {
            return false;
        }
        else
        {
            ret->_status = DELETE;  //伪删除
            _n--;
            return true;
        }
    }
};

}

namespace bucket_hash {

template <class T>
struct HashNode
{
    T _data;
    HashNode<T>* _next;
    
    HashNode(const T& data)
        : _data(data)
        , _next(nullptr)
    {}
};

template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return key;
    }
};

//特化——对string类型进行单独处理
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for(size_t i = 0; i < key.size(); i++)
        {
            hash *= 131;        //BKDR Hash思想
            hash += key[i];
        }
        return hash;
    }
};

size_t GetNextPrime(size_t prime)
{
    const int PRIMECOUNT = 28;
    static const size_t primeList[PRIMECOUNT] =
    {
        53ul, 97ul, 193ul, 389ul, 769ul,
        1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
        49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
        1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
        50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
        1610612741ul, 3221225473ul, 4294967291ul
    };

    size_t i = 0;
    for (; i < PRIMECOUNT; ++i)
    {
        if (primeList[i] > prime)
            return primeList[i];
    }

    return primeList[i];
}

//前置声明：解决哈希表和哈希迭代器的互相引用的问题
template <class K, class T, class Hash, class KeyOfT>
class HashTable;

template <class K, class T, class Hash, class KeyOfT>
struct HTIterator
{
    typedef HashNode<T> Node;
    typedef HashTable<K, T, Hash, KeyOfT> HT;
    typedef HTIterator<K, T, Hash, KeyOfT> Self;
    Node* _node;
    HT* _ht;
    
    HTIterator(Node* node, HT* ht)
        :_node(node)
        , _ht(ht)
    {}
    
    bool operator!=(const Self& s) const
    {
        return _node != s._node;
    }
    
    T& operator*()
    {
        return _node->_data;
    }
    
    T* operator->()
    {
        return &(_node->_data);
    }
    
    Self operator++()
    {
        if(_node->_next)    //在当前桶迭代
        {
            _node = _node->_next;
        }
        else    //找下一个桶
        {
            KeyOfT kot;
            Hash hf;
            const K& key = kot(_node->_data);
            size_t index = hf(key) % _ht->_tables.size();
            ++index;
            while(index < _ht->_tables.size())
            {
                if(_ht->_tables[index])
                {
                    _node = _ht->_tables[index];
                    break;
                }
                else
                {
                    index++;
                }
            }
            if(index == _ht->_tables.size())    //后面没有桶了
            {
                _node = nullptr;
            }
        }
        return *this;
    }
    
};

template <class K, class T, class Hash, class KeyOfT>
class HashTable
{
    typedef HashNode<T> Node;
    
    friend struct HTIterator<K, T, Hash, KeyOfT>;
private:
    vector<Node*> _tables;
    size_t _n = 0;  //存储多少有效数据
    
public:
    typedef HTIterator<K, T, Hash, KeyOfT> iterator;
    
    iterator begin()
    {
        for(size_t i = 0; i < _tables.size(); i++)
        {
            if(_tables[i])
            {
                return iterator(_tables[i], this);
            }
        }
        return end();
    }
    
    iterator end()
    {
        return iterator(nullptr, this);
    }
    
    ~HashTable()
    {
        for(size_t i = 0; i < _tables.size(); i++)
        {
            Node* cur = _tables[i];
            while(cur)
            {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
    }
    
    bool Erase(const K& key)
    {
        if(_tables.size() == 0)
        {
            return false;
        }
        Hash hf;
        KeyOfT kot;
        size_t index = hf(key) % _tables.size();
        Node* cur = _tables[index];
        Node* prev = nullptr;
        while(cur)
        {
            if(kot(cur->_data) == key)
            {
                //1. 删除的是头节点
                //2. 删除的是非头节点
                if(prev == nullptr)
                {
                    _tables[index] = cur->_next;
                }
                else
                {
                    prev->_next = cur->_next;
                }
                delete cur;
                --_n;
                return true ;
            }
            else
            {
                prev = cur;
                cur = cur->_next;
            }
        }
        return false;
    }
    
    Node* Find(const K& key)
    {
        if(_tables.size() == 0)
        {
            return nullptr;
        }
        Hash hf;
        KeyOfT kot;
        size_t index = hf(key) % _tables.size();
        Node* cur = _tables[index];
        while(cur)
        {
            if(kot(cur->_data) == key)
            {
                return cur;
            }
            else
            {
                cur = cur->_next;
            }
        }
        return nullptr;
    }
    
    pair<iterator, bool> insert(const T& data)
    {
        Hash hf;
        KeyOfT kot;
        if(_tables.size() == _n)
        {
//            size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
            size_t newSize = GetNextPrime(_tables.size());  //使用素数表进行增容，素数大小的空间可能会提高效率
            vector<Node*> newtables(newSize);
            for(size_t i = 0; i < _tables.size(); i++)
            {
                Node* cur = _tables[i];
                while(cur)
                {
                    Node* next = cur->_next;
                    
                    const K& key = kot(cur->_data);
                    size_t index = hf(key) % newSize;
                    cur->_next = newtables[index];
                    newtables[index] = cur;
                    
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            newtables.swap(_tables);
        }
        const K& key = kot(data);
        size_t index = hf(key) % _tables.size();
        Node* cur = _tables[index];
        while(cur)
        {
            if(kot(cur->_data) == kot(data))
            {
                return make_pair(iterator(cur, this), false);
            }
            else
            {
                cur = cur->_next;
            }
        }
        Node* newnode = new Node(data);
        newnode->_next = _tables[index];
        _tables[index] = newnode;
        _n++;
        
        return make_pair(iterator(newnode, this), true);
    }
};

}
